package leetcode_day._2022._202203._2131;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/31 23:06
 * 自除数
 * 算法：打表 + 二分
 */
public class _31_728 {

    static List<Integer> list;
    static {
        list = new ArrayList<>();
        out:for (int i = 1; i <= 100000; i++) {
            int tmp = i;
            while (tmp != 0) {
                int t = tmp % 10;
                if (t == 0 || i % t != 0) continue out;
                tmp /= 10;
            }
            list.add(i);
        }
    }
    public List<Integer> selfDividingNumbers(int left, int right) {
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int mid = l + r>> 1;
            if (list.get(mid) >= left) r = mid;
            else l = mid + 1;
        }
        List<Integer> ans = new ArrayList<>();
        while (l < list.size() && list.get(l) <= right) ans.add(list.get(l++));
        return ans;
    }

}
